package features.advance.leetcode.interview.offer.easy;


import java.util.Arrays;
import java.util.Random;

/**
 *  剑指 Offer 11. 旋转数组的最小数字
 *
 *  难度：简单
 *
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
 * 例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
 *
 * 示例 1：
 *
 * 输入：[3,4,5,1,2]
 * 输出：1
 * 示例 2：
 *
 * 输入：[2,2,2,0,1]
 * 输出：0
 * 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
 *
 * @author LIN
 * @date 2021-05-13
 */
public class Offer11 {

    public int minArray(int[] numbers) {
        int n = numbers.length;
        int result = numbers[0];
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = (l + r + 1) >> 1;
            // 左值等于中间值，就把左边界向右移动一位
            if(numbers[l] == numbers[mid]){
                result = Math.min(result, numbers[mid]);
                l++;
                // 左值小于中间值，就忽略左区间
            }else if(numbers[l] < numbers[mid]){
                result = Math.min(result, numbers[l]);
                l = mid  + 1;
            }else{
                // 如果左值大于中间值，就忽略右区间
                result = Math.min(result, numbers[mid]);
                r = mid  - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Offer11 offer11 = new Offer11() {
            @Override
            public int minArray(int[] numbers) {
                return super.minArray(numbers);
            }
        };
        Random random = new Random();
        int n = 20000;
        int[] a = new int[n];
        int[] b = new int[n/2];
        for (int i = 0; i < n/2; i++) {
            a[i] = random.nextInt();
        }
        Arrays.sort(a);
        for (int i = 0; i < n/2; i++) {
            b[i] = random.nextInt();
        }
        Arrays.sort(b);
        for (int i = n/2; i < n; i++) {
            a[i] = b[i - n/2];
        }

        int[] numbers = {3,4,5,1,2};
        numbers = a;
        int minArray = offer11.minArray(numbers);
        System.out.println(minArray);
    }
}
